\relax 
\citation{PT09}
\citation{Miy01}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\newlabel{s:intro}{{1}{1}}
\citation{Bar01}
\citation{Moul80}
\citation{SV02}
\citation{PT09}
\citation{PT09}
\citation{SV02}
\citation{PT09}
\citation{LWZ09}
\citation{LSWZ10}
\citation{LSWZ10}
\citation{LSWZ10}
\citation{PT09}
\citation{PT09,LWZ09,LSWZ10}
\citation{Kouts11}
\citation{Moul80}
\citation{LSWZ10}
\citation{Moul80}
\citation{Miy01}
\citation{BB06,Ju08}
\citation{AFPT09}
\citation{FW11}
\citation{FW11}
\citation{EGTPS11}
\citation{NST10}
\citation{NST10}
\citation{MT07}
\citation{FT10}
\citation{LSWZ10}
\citation{Moul80}
\@writefile{toc}{\contentsline {section}{\numberline {2}Notation, Definitions, and Preliminaries}{5}}
\newlabel{s:prelim}{{2}{5}}
\citation{LSWZ10}
\newlabel{prop:middle}{{2.1}{6}}
\newlabel{prop:interval}{{2.2}{6}}
\newlabel{prop:right_cover}{{2.3}{6}}
\citation{LSWZ10}
\citation{LSWZ10}
\citation{PT09}
\newlabel{prop:left_cover}{{2.4}{7}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Strategyproof Mechanisms for the 2-Facility Location Game: Outline}{7}}
\newlabel{s:2facilities}{{3}{7}}
\newlabel{thm:2fac-gen}{{3.1}{7}}
\newlabel{cor:2fac-anonymous}{{3.2}{7}}
\newlabel{cor:2fac-approx}{{3.3}{7}}
\newlabel{thm:3agents}{{3.4}{7}}
\citation{Moul80}
\citation{SV07}
\newlabel{thm:3locations}{{3.5}{8}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Allocating 2 Facilities to 3 Agents: The Proof of Theorem\nobreakspace  {}3.4\hbox {}}{8}}
\newlabel{s:3agents}{{4}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Outline of the Proof}{8}}
\newlabel{s:outline}{{4.1}{8}}
\newlabel{fig:allocation}{{1}{9}}
\citation{SV07}
\citation{SV07}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Well-Separated Instances}{10}}
\newlabel{s:well-separated}{{4.2}{10}}
\newlabel{l:single-p}{{4.1}{10}}
\newlabel{l:i-separated}{{4.2}{10}}
\newlabel{cor:dict-location}{{4.3}{11}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}General Instances and the Range of the Threshold $p$}{11}}
\newlabel{s:gen-instances}{{4.3}{11}}
\newlabel{l:non-separated}{{4.4}{11}}
\newlabel{l:non-separated-inside}{{4.5}{11}}
\newlabel{l:approx}{{4.6}{11}}
\newlabel{fig:instances}{{2}{12}}
\newlabel{l:i-cases}{{4.7}{12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.4}On the Existence of a Partial Dictator}{13}}
\newlabel{s:3agent-fin}{{4.4}{13}}
\newlabel{prop:dict-location-a}{{4.8}{13}}
\newlabel{l:always-a}{{4.9}{13}}
\newlabel{l:others-a}{{4.10}{13}}
\newlabel{l:only-dictator}{{4.11}{13}}
\newlabel{l:3agents}{{4.12}{13}}
\citation{LSWZ10}
\@writefile{toc}{\contentsline {section}{\numberline {5}Allocating 2 Facilities to 3 Locations: The Proof of Theorem\nobreakspace  {}3.5\hbox {}}{14}}
\newlabel{s:3locations}{{5}{14}}
\newlabel{cor:3agents}{{5.1}{14}}
\newlabel{l:any-partition}{{5.2}{15}}
\newlabel{l:unique-dictator-small}{{5.3}{15}}
\citation{LSWZ10}
\newlabel{l:unique-dictator-large}{{5.4}{16}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Strategyproof Allocation of 2 Facilities: The Proof of Theorem\nobreakspace  {}3.1\hbox {}}{16}}
\newlabel{s:2fac-gen}{{6}{16}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Inexistence of Anonymous Nice Mechanisms for More Than 2 Facilities}{17}}
\newlabel{s:3facilities}{{7}{17}}
\newlabel{thm:3facilities}{{7.1}{17}}
\bibstyle{acmsmall}
\bibdata{mechdesign}
\bibcite{AFPT09}{\citeauthoryear {Alon, Feldman, Procaccia, and Tennenholtz}{Alon et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2010}}
\bibcite{Bar01}{\citeauthoryear {Barber\`{a}}{Barber\`{a}}{2001}}
\bibcite{BB06}{\citeauthoryear {Barber\`{a} and Bevi\'{a}}{Barber\`{a} and Bevi\'{a}}{2006}}
\bibcite{EGTPS11}{\citeauthoryear {Escoffier, Gourv\`{e}s, Thang, Pascual, and Spanjaard}{Escoffier et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2011}}
\bibcite{FW11}{\citeauthoryear {Feldman and Wilf}{Feldman and Wilf}{2011}}
\bibcite{FT10}{\citeauthoryear {Fotakis and Tzamos}{Fotakis and Tzamos}{2010}}
\bibcite{Ju08}{\citeauthoryear {Ju}{Ju}{2008}}
\bibcite{Kouts11}{\citeauthoryear {Koutsoupias}{Koutsoupias}{2011}}
\bibcite{LSWZ10}{\citeauthoryear {Lu, Sun, Wang, and Zhu}{Lu et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2010}}
\bibcite{LWZ09}{\citeauthoryear {Lu, Wang, and Zhou}{Lu et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2009}}
\bibcite{MT07}{\citeauthoryear {McSherry and Talwar}{McSherry and Talwar}{2007}}
\bibcite{Miy01}{\citeauthoryear {Miyagawa}{Miyagawa}{2001}}
\bibcite{Moul80}{\citeauthoryear {Moulin}{Moulin}{1980}}
\bibcite{NST10}{\citeauthoryear {Nissim, Smorodinsky, and Tennenholtz}{Nissim et\nobreakspace  {}al\unhbox \voidb@x \hbox {.}}{2010}}
\bibcite{PT09}{\citeauthoryear {Procaccia and Tennenholtz}{Procaccia and Tennenholtz}{2009}}
\bibcite{SV02}{\citeauthoryear {Schummer and Vohra}{Schummer and Vohra}{2002}}
\bibcite{SV07}{\citeauthoryear {Schummer and Vohra}{Schummer and Vohra}{2007}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Discussion and Open Problems}{18}}
\@writefile{toc}{\contentsline {section}{\numberline {A}Appendix\nobreakspace  {}A\hbox {}: Dealing with Well-Separated Instances}{19}}
\newlabel{app:moves}{{A}{19}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.1}The Proof of Proposition\nobreakspace  {}2.1\hbox {}}{19}}
\newlabel{app:s:middle}{{A.1}{19}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.2}The Proof of Proposition\nobreakspace  {}2.2\hbox {}}{19}}
\newlabel{app:s:interval}{{A.2}{19}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.3}Pushing the Pair of the Rightmost Agents to the Right: The Proof of Proposition\nobreakspace  {}2.3\hbox {}}{19}}
\newlabel{app:s:push_right}{{A.3}{19}}
\newlabel{prop:b_pushes_c}{{A.1}{19}}
\newlabel{prop:c_pulls_b}{{A.2}{19}}
\newlabel{prop:right_cover_step}{{A.3}{20}}
\newlabel{prop:right_cover_3agents}{{A.4}{20}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.4}Pushing the Pair of the Rightmost Agents to the Left: The Proof of Proposition\nobreakspace  {}2.4\hbox {}}{20}}
\newlabel{app:s:push_left}{{A.4}{20}}
\newlabel{prop:c_pushes_b}{{A.5}{20}}
\newlabel{prop:b_pulls_c}{{A.6}{21}}
\newlabel{prop:left_cover_step}{{A.7}{21}}
\newlabel{prop:left_cover_3agents}{{A.8}{21}}
\@writefile{toc}{\contentsline {section}{\numberline {B}Appendix\nobreakspace  {}B\hbox {}: Proofs Missing from Section\nobreakspace  {}4\hbox {}}{22}}
\newlabel{app:s:3agents}{{B}{22}}
\@writefile{toc}{\contentsline {subsection}{\numberline {B.1}The Proof of Lemma\nobreakspace  {}4.1\hbox {}}{22}}
\newlabel{app:s:single-p}{{B.1}{22}}
\newlabel{eq:p-median}{{1}{22}}
\newlabel{cl:moving-backwards}{{B.1}{23}}
\@writefile{toc}{\contentsline {subsection}{\numberline {B.2}The Proof of Lemma\nobreakspace  {}4.2\hbox {}}{23}}
\newlabel{app:s:i-separated}{{B.2}{23}}
\@writefile{toc}{\contentsline {subsection}{\numberline {B.3}The Proof of Corollary\nobreakspace  {}4.3\hbox {}}{24}}
\newlabel{app:s:dict-location}{{B.3}{24}}
\@writefile{toc}{\contentsline {subsection}{\numberline {B.4}The Proof of Lemma\nobreakspace  {}4.5\hbox {}}{24}}
\newlabel{app:s:non-separated-inside}{{B.4}{24}}
\@writefile{toc}{\contentsline {subsection}{\numberline {B.5}The Proof of Lemma\nobreakspace  {}4.10\hbox {}}{24}}
\newlabel{app:s:others-a}{{B.5}{24}}
\@writefile{toc}{\contentsline {subsection}{\numberline {B.6}The Proof of Lemma\nobreakspace  {}4.11\hbox {}}{24}}
\newlabel{app:s:only-dictator}{{B.6}{24}}
\@writefile{toc}{\contentsline {subsection}{\numberline {B.7}The Rest of the Proof of Lemma\nobreakspace  {}4.12\hbox {}}{25}}
\newlabel{app:s:3agents-lemma}{{B.7}{25}}
\@writefile{toc}{\contentsline {section}{\numberline {C}Appendix\nobreakspace  {}C\hbox {}: Proofs Missing from Section\nobreakspace  {}5\hbox {}}{26}}
\newlabel{app:s:3locations}{{C}{26}}
\@writefile{toc}{\contentsline {subsection}{\numberline {C.1}A Detailed Proof of Lemma\nobreakspace  {}5.2\hbox {}}{26}}
\newlabel{app:s:any-partition}{{C.1}{26}}
\@writefile{toc}{\contentsline {subsection}{\numberline {C.2}Details Missing from the Proof of Lemma\nobreakspace  {}5.3\hbox {}}{27}}
\newlabel{app:s:unique-dictator-small}{{C.2}{27}}
\@writefile{toc}{\contentsline {subsection}{\numberline {C.3}The Proof of Lemma\nobreakspace  {}5.4\hbox {}}{28}}
\newlabel{app:s:unique-dictator-large}{{C.3}{28}}
\newlabel{cl:remove-agent-claim}{{C.1}{28}}
\lastpage{29}
\@writefile{toc}{\contentsline {section}{\numberline {D}Appendix\nobreakspace  {}D\hbox {}: Details Missing from the Proof of Theorem\nobreakspace  {}7.1\hbox {}}{29}}
\newlabel{app:s:3fac}{{D}{29}}
\@writefile{toc}{\contentsline {subsection}{\numberline {D.1}Proof of Theorem\nobreakspace  {}7.1\hbox {}: Case where $F_3(\mathaccentV {vec}17E{x}) = x_3$}{29}}
\newlabel{app:s:3facilities}{{D.1}{29}}
